#include <iterator>
#include <string>
#include <sstream>


#include "grid.h"
#include <iosfwd>
#include <algorithm>
#include <vector>
#include <numeric>
#include <exception>

#include "polygon.h"


polygon_t::polygon_t()
{
}

void polygon_t::add(contour_t const & ring)
{
    contours_.push_back(ring);
}

contour_t const & polygon_t::operator[] (size_t i) const
{
    return contours_[i];
}

size_t polygon_t::size() const
{
    return contours_.size();
}

std::ostream & operator<<(std::ostream & out, polygon_t const & polygon)
{
    for (size_t i = 0; i < polygon.contours_.size(); ++i)
    {
        out << polygon.contours_[i];
    }
    out << std::endl;
    return out;
}

std::istream & operator>>(std::istream & in, polygon_t & polygon)
{
    polygon_data_t polygon_data;
    in >> polygon_data;
    try
    {
        polygon = get_polygon(polygon_data);
    }
    catch (std::exception exc)
    {
        std::cout << exc.what() << std::endl;
        return in;
    }
    return in;
}


///polygon_data_t

point_t * find(point_t const & point, polygon_data_t & polygon_data) {
    for(size_t i = 0; i < polygon_data.size(); ++i) {
        point_t * answer = find(point, polygon_data[i]);
        if(answer != 0) return answer;
    }
    return 0;
}

point_t top_left_corner(polygon_data_t const & polygon_data)
{
    if(polygon_data.size() != 0) {
        point_t corner = top_left_corner(polygon_data[0]);
        std::vector<contour_data_t>::const_iterator i = polygon_data.begin() + 1;
        double min_x = corner.x;
        double min_y = corner.y;
        for(; i != polygon_data.end(); ++i)
        {
            point_t current_corner = top_left_corner(*i);
            if (min_x > current_corner.x)
            {
                min_x = current_corner.x;
            }
            if (min_y > current_corner.y)
            {
                min_y = current_corner.y;
            }
        }
        return point_t(min_x, min_y);
    }
    return point_t(0, 0);
}

point_t bottom_right_corner(polygon_data_t const & polygon_data)
{
    if(polygon_data.size() != 0) {
        point_t corner = bottom_right_corner(polygon_data[0]);
        std::vector<contour_data_t>::const_iterator i = polygon_data.begin() + 1;
        double max_x = corner.x;
        double max_y = corner.y;
        for(; i != polygon_data.end(); ++i)
        {
            point_t current_corner = bottom_right_corner(*i);
            if (max_x < current_corner.x)
            {
                max_x = current_corner.x;
            }
            if (max_y < current_corner.y)
            {
                max_y = current_corner.y;
            }
        }
        return point_t(max_x, max_y);
    }
    return point_t(0, 0);
}

std::ostream & operator<<(std::ostream & out, polygon_data_t const & polygon_data)
{
    for (size_t i = 0; i < polygon_data.size(); ++i)
    {
        out << polygon_data[i];
    }
    out << std::endl;
    return out;
}

std::istream & operator>>(std::istream & in, polygon_data_t & polygon_data)
{
    while (!in.eof())
    {
        std::string buff;
        std::getline(in, buff);
        if (buff == "") break;
        std::stringstream ss(buff);
        std::string s = ss.str();
        if (!ss.eof())
        {
            contour_data_t contour;
            ss >> contour;
            polygon_data.push_back(contour);
        }
    }
    return in;
}

polygon_t get_polygon(polygon_data_t const & polygon_data)
{
    std::vector<contour_t> answer;
    std::vector<contour_data_t>::const_iterator i = polygon_data.begin();
    
    grid_t grid(1000);
    inserter_without_intersections f;

    if(polygon_data.size() > 0)
    {
        inserter ins;
        contour_t contour = get_contour(*(i));
        grid.visit(contour, ins);
        double max_diameter = abs(top_left_corner(*i).x - bottom_right_corner(*i).x);
        answer.push_back(contour);

        ++i;
        for(; i != polygon_data.end(); ++i)
        {
            bool flag = true;
            contour = get_contour(*i);
            try
            {
                grid.visit(contour, f);
            }
            catch(std::exception)
            {
                flag = false;
            }

            if(flag)
            {
                answer.push_back(contour);
                double diameter = abs(top_left_corner(*i).x - bottom_right_corner(*i).x);
                if(diameter > max_diameter)
                {
                    std::swap(answer[0], answer[answer.size() - 1]);
                    max_diameter = diameter;
                }
                answer[answer.size() - 1].direction(COUNTERCLOCKWISE);
            }
        }
        answer[0].direction(CLOCKWISE);
    }
    return polygon_t(answer.begin(), answer.end());
}
